package offer;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class offerII_0085 {
    public List<String> generateParenthesis(int n) {
        List<String> result=new LinkedList<>();
        List<Character> path=new LinkedList<>();
        Stack<Character> stack=new Stack<>();
        search(result,path,stack,n,n);
        return result;
    }
    public void search(List<String> result,List<Character> path,Stack<Character> stack,int left,int right){
        if(stack.size()>left+right) return;
        if(left==0&&right==0){
            String s="";
            for(int i=0;i<path.size();++i){
                s+=path.get(i);
            }
            result.add(s);
            return;
        }
        if(left>0){
            Stack<Character> tmp= (Stack<Character>) stack.clone();
            tmp.push('(');
            path.add('(');
            search(result, path, tmp, left-1, right);
            path.remove(path.size()-1);
        }
        if(right>0){
            Stack<Character> tmp= (Stack<Character>) stack.clone();
            if(!tmp.isEmpty()&&tmp.peek()=='('){
                tmp.pop();
            }
            else tmp.push(')');
            path.add(')');
            search(result, path, tmp, left, right-1);
            path.remove(path.size()-1);
        }
    }
}
